package algotithm.leetcode.dp.hot.test131;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/9-18:42
 * @Title 131. 分割回文串
 * @URL https://leetcode-cn.com/problems/palindrome-partitioning/
 */
public class Solution {

    public static void main(String[] args) {
        String s = "aab";
        Solution solution = new Solution();
        List<List<String>> list = solution.partition(s);
        System.out.println(list);
    }

    public List<List<String>> partition(String s) {
        List<List<String>> list = new ArrayList<>();
        Deque<String> stack  = new ArrayDeque<>();
        int len = s.length();
        bfs(s,0,len,stack,list);
        return list;
    }

    public void bfs (String s, int start, int len, Deque<String> path, List<List<String>> list) {
        // 终止条件
        if (start == len) {
            list.add(new ArrayList<String>(path));
            return;
        }
        for (int i = start; i < len; i++) {
            // 如果当前从start到i的不是回文串那就继续探索下一个
            // 这里当然也可以用dp来判断是否是回文串，但是需要额外的O（n）的空间
            if (!check(s,start,i)) {
                continue;
            }
            path.addLast(s.substring(start,i+1));
            bfs(s,i+1,len,path,list);
            // 剪枝
            path.removeLast();
        }
    }

    /**
     *
     * @param s 字符串
     * @param i 字符串的起始位置
     * @param j 字符串的末尾位置
     * @return 布尔类型的值
     */
    public boolean check(String s,int i, int j) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}
